package leetcode.code0124;

import leetcode.helper.tree.TreeNode;

public class Solution1 extends Solution124 {

	class Info {
		int l;// 左子树不跨过头结点的最大值
		int r;// 右子树不跨过头结点的最大值
		int root;// 经过头结点的最大值
	}

	@Override
	public int maxPathSum(TreeNode root) {
		Info info = this.max(root);
		return info.root;
	}

	private Info max(TreeNode root) {
		Info ans = new Info();
		if (root.left == null && root.right == null) {
			ans.l = root.val;
			ans.r = root.val;
			ans.root = root.val;
			return ans;
		}
		if (root.left != null && root.right == null) {
			Info left = this.max(root.left);
			ans.l = Math.max(Math.max(left.l, left.r) + root.val, root.val);// 当前左子树不跨过头结点的最大值 = 左侧不跨节点中最大的 + 当前节点
			ans.r = root.val;
			ans.root = Math.max(left.root, ans.l);// 左树,右树,跨过头结点中最大的
			return ans;
		}
		if (root.left == null && root.right != null) {
			Info right = this.max(root.right);
			ans.l = root.val;// 当前左子树不跨过头结点的最大值 = 左侧不跨节点中最大的 + 当前节点
			ans.r = Math.max(Math.max(right.l, right.r) + root.val, root.val);
			ans.root = Math.max(right.root, ans.r);// 左树,右树,跨过头结点中最大的
			return ans;
		}
		// if (root.left != null && root.right != null)
		Info left = this.max(root.left);
		Info right = this.max(root.right);
		ans.l = Math.max(Math.max(left.l, left.r) + root.val, root.val);// 当前左子树不跨过头结点的最大值 = 左侧不跨节点中最大的 + 当前节点
		ans.r = Math.max(Math.max(right.l, right.r) + root.val, root.val);
		ans.root = Math.max(Math.max(left.root, right.root), ans.l + ans.r - root.val);// 左树,右树,跨过头结点中最大的
		return ans;
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
	}

}
